DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2016.10

Trading Determinism for Time in Space Bounded Computations

Authors: Vivek Anand T Kallampally and Raghunath Tewari

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract

Savitch showed in 1970 that nondeterministic logspace (NL) is contained in deterministic O(log^2(n)) space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open. In this paper we give a partial solution to this problem and show that for every language in NL there exists an unambiguous nondeterministic algorithm that requires O(log^2(n)) space and simultaneously runs in polynomial time.

Cite as

Vivek Anand T Kallampally and Raghunath Tewari. Trading Determinism for Time in Space Bounded Computations. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kallampally_et_al:LIPIcs.MFCS.2016.10,
  author =	{Kallampally, Vivek Anand T and Tewari, Raghunath},
  title =	{{Trading Determinism for Time in Space Bounded Computations}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.10},
  URN =		{urn:nbn:de:0030-drops-64268},
  doi =		{10.4230/LIPIcs.MFCS.2016.10},
  annote =	{Keywords: space complexity, unambiguous computations, Savitch's Theorem}
}

Search Results

Documents authored by Kallampally, Vivek Anand T

Trading Determinism for Time in Space Bounded Computations

Abstract

Cite as

Thanks for your feedback!

Could not send message